/**
 * 
 */
package array.passed2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class ThreeSum {
	/**
	Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

	Note:

	Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
	The solution set must not contain duplicate triplets.
	For example, given array S = {-1 0 1 2 -1 -4},

	A solution set is:
	(-1, 0, 1)
	(-1, -1, 2)
	 */
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> solutions = new ArrayList<>();
        if (num == null || num.length < 3)
            return solutions;
        Arrays.sort(num);
        for (int i = 0, to = num.length - 3; i <= to; i++) {
            if (i > 0 && num[i] == num[i - 1]) continue;
            int left = i + 1, right = num.length - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                if (sum == 0) {
                    solutions.add(Arrays.asList(num[i], num[left], num[right]));                  
                    while (left < right && num[left] == num[left + 1]) left++;
                    while (right > left && num[right] == num[right - 1]) right--;
                    left++;
                    right--;
                }
                else if (sum < 0) {
                    left++;
                }
                else { // sum > 0
                    right--;
                }
            }
        }
        
        return solutions;
    }
    
	public ArrayList<ArrayList<Integer>> threeSum1(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num == null || num.length < 3)
			return result;
		Arrays.sort(num);
		for (int i = 0; i < num.length - 2; i++) {
			while (i > 0 && num[i] == num[i - 1]) continue;
			int start = i + 1;
			int end = num.length - 1;
			while (start < end) {
				int sum = num[i] + num[start] + num[end];
				if (sum == 0) {
					ArrayList<Integer> list = new ArrayList<Integer>();
					list.add(num[i]);
					list.add(num[start]);
					list.add(num[end]);
					result.add(list);
					start++;
					end--;
					// to remove the duplicate number for each while loop
					while (start < end && num[start] == num[start - 1])
						start++;
					while (start < end && num[end] == num[end + 1])
						end--;
				} else if (sum < 0) {
					start++;
				} else { // sum > 0
					end--;
				}
			}
			// to remove duplicated number outshide the while loop
			while (i < num.length - 1 && num[i] == num[i + 1])
				i++;
		}

		return result;
	}

	/**
	 * 
	 */
	public ThreeSum() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
